package hashmap;

import java.util.*;

public class SortCharByOccurence451 {


    public static String frequencySort(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (!map.containsKey(s.charAt(i)))
                map.put(s.charAt(i), 1);
            else
                map.put(s.charAt(i), map.get(s.charAt(i)) + 1);
        }
        PriorityQueue<Tuple> heap = new PriorityQueue<>(new Comparator<Tuple>() {
            @Override
            public int compare(Tuple o1, Tuple o2) {
                return o2.count - o1.count;
            }
        });
        for(Map.Entry e:map.entrySet())
            heap.add(new Tuple((char)e.getKey(),(int)e.getValue()));

        while(!heap.isEmpty()){
            Tuple t = heap.poll();
            for(int i = 0; i < t.count; i++)
                stringBuilder.append(t.character);
        }
        return stringBuilder.toString();
    }
    static class Tuple{
        char character;
        int count;
        public  Tuple(char ch, int count){
            this.character = ch;
            this.count = count;
        }
    }
    public static String frequencySortTreeMap(String s) {
        StringBuilder sb = new StringBuilder();
        return sb.toString();
    }

    public static void main(String[] args) {
        System.out.println(frequencySort("ddsssswer"));
    }
}
